----------------------------------------Day1下午：STL容器-----------------------------------------
一、认识STL（初赛知识）
C++标准库的一部分，用于实现数据类型算法。
STL容器属于一种数据类型，用于存储。
常见的容器有map、set、list、queue、vector、stack等。
二、map容器（T20416.计数员、T20417.幸运数对、T20421.密文搜索）
map是一种关联容器用于存储映射关系，可用多种数据类型表示其下标。
每个下标是唯一的，可用于用键查找值的场景。（键即下标）
如果键不存在，会自动扩展一个空间；若已存在，则会更换数值。
map可开辟无数个空间，不会造成空间浪费。
map会按照其下标字典序进行自动排序，与插入顺序无关。（从小到大）
头文件：#include<map>
定义：map<键类型,值类型> 容器名;
存值：容器名[下标（键）] = 值;
查值：容器名[下标（键）]
使用迭代器访问map时，.first是键，.second是值
获取首元素：(*it).first
获取尾元素：(*it).second
插入元素：容器名.insert(插入内容)
删除元素：容器名.erase(删除内容)
查找空间数量：容器名.size()
清空元素：容器名.clear()
判断是否为空：容器名.empty()
查找迭代器是否存在：容器名.find(查找内容)
三、迭代器（T20416.计数员、T20418.宝物管理）
提供一种统一的方式来访问容器中元素的方式，STL大多容器都支持迭代器。
it最初为一个地址，需使用*进行解析，迭代器可用auto来替换。
auto可将it直接变成容器里的实际数据。
定义：容器定义::iterator 迭代器名;
查找首元素：it.begin()
查找尾元素：it.end()-1
创建：for(it = 容器名.begin();it != 容器名.end();it++)
auto用法：for(auto it : 容器名)
四、set容器（T20418.宝物管理、T20419.明明的随机数、T20422.复制）
set是一种关联容器，是一个有序、不允许重复元素的容器。（可自动去重并排序）
set也会按照其下标字典序进行自动排序。（从小到大，结构体亦此）
set也可以使用迭代器（auto）进行遍历。
使用数值作为删除依据的时间复杂度为O(logn)，迭代器删除依据的时间复杂度为O(1)。
头文件：#include<set>
定义：set<数据类型> 容器名;
插入元素：容器名.insert(插入内容)
删除元素：容器名.erase(删除内容)
查找空间数量：容器名.size()
清空元素：容器名.clear()
判断是否为空：容器名.empty()
查找迭代器是否存在：容器名.find(查找内容)
五、vector容器（T20420.输出所有约数、T20423.出边的排序）
vector是一种可以自动扩容的STL容器，与数组相似。（最多可存放1e9个元素）
vector内所有值的初始值都为0。
当加入元素时，vector会自动将元素加入下标0的位置。
push_back()是从后往前压入vector容器的。
初始值会将vector中所有值变为该值。
头文件：#include<vector>
普通定义：vector<数据类型> 容器名;
初始化空间定义：vector<数据类型> 容器名(空间大小);
初始值定义：vector<数据类型> 容器名(空间大小,初始值);
查找下标值：容器名[下标]
插入元素：容器名.push_back(插入内容)
第一个元素：容器名.front()
最后一个元素：容器名.back()
找空间数量：容器名字.size()
调整大小：容器名.resize(调整后的大小)
预分配内存：容器名.reserve(预分配的内存)
获取首元素：容器名.first()
获取尾元素：容器名.end()
普通数组遍历：for(int i = 1;i <= 容器名.size();i++)
迭代器遍历：for(auto i : 容器名)
六、priority_queue容器（T20422.复制）
优先队列是一种容器适配器，每次访问的是具有最高优先级的元素。
与队列一样，队头出队，对位入队，但会维护优先级。
排序规则有greater（从小到大）和less（从大到小）。
普通定义：priority_queue<数据类型> 容器名;
自定义定义：priority_queue<数据类型,vector<int>,排序规则<int>>
删除最高级：容器名.pop()
添加元素：容器名.push()
查找队头元素：容器名.top()
判断是否为空：容器名.empty()
----------------------------------------Day2下午：高精度算法-----------------------------------------
一、高精度算法（T20451.高精度加法、T20452.高精度减法、T19485.高精度乘法...）
指当我们要计算的数字无法使用基础类型存储时的计算方法，一般数字很大。（模拟）
我们常将数位分离，并用字符串数组string来倒序存储数据。（除法除外）
高精度算法中，0下标为个位、1下标为十位、2下标为百位，以此类推。
二、高精度加法（T20451.高精度加法）
指模拟数学计算时，竖式计算加法的过程。（从高位往低位计算）
过程：1.储存数字；2.同位相加（考虑进位）；3.输出结果（去前导0）。
三、高精度减法（T20452.高精度减法）
指模拟数学计算时，竖式计算减法的过程。（从高位往低位计算）
过程：1.储存数字（判断符号）；2.同位相减（考虑借位）；3.输出结果（去前导0）。
四、高精度乘法（T20448.高精度乘低精度、T19485.高精度乘法）
指模拟数学计算时，竖式计算乘法的过程。（从高位往低位计算）
高精乘分为高精乘高精和低精乘低精。（常为高精乘高精）
过程：1.储存数字；2.同位相乘（考虑进位）；3.输出结果（去前导0）。
五、高精度除法（T20450.高精度除法）
指模拟数学计算时，竖式计算除法的过程。（从高位往低位计算）
当除数或被除数可以用基础类型储存时，可将其作为整体进行计算。
过程：1.储存数字；2.同位相除（考虑借位）；3.输出结果（去前导0）。
高精除不需要逆序存储。（不需要数位对齐）
----------------------------------------Day3下午：算法基础-----------------------------------------
一、双指针（T20459.双指针1、T20458.双指针2）
双指针是指利用两个游标的方式，在序列上进行维护。（贪心、二分均利用此方法）
双指针不属于一种算法，而是一种以两个变量进行框定区间的思路。
二、差分（T19465.区间修改模板题）
差分是前缀和的逆运算，从后往前进行序列的分割，并求两个相邻元素的差值。
对于某个数组a，存在差分数组d，使得d的前缀和，可以获得a。
当在差分位置i的d[i]增加c时，其对应的原数据在i位置的a[i]也增加c。
区间修改问题是指对序列[L,R]区间上的每个元素都增加一个c。
d[i] = a[i] - a[i - 1]
a[i] + c = d[i] + c
三、倍增（T20457.RMQ、T20460.积木大赛）
即成倍增加，一般用于处理数据很大不能使用枚举解决的问题。
ST稀疏表采用倍增的思想处理RMQ问题。（每查询一次，时间复杂度为O(1)；最终时间复杂度为O(nlogn)）
建表基础思想：设F[i][j]表示区间[i,i + 2^j - 1]区间的最值，区间长度为2^j。
根据倍增思想：长度为2j的区间可以被分为两个长度为2^j-1的子区间。递推公式：F[i][j] = max(F[i][j - 1],F[i + 2^j-1][j - 1])。
ST创建：若数组长度为n，则有2^k ≤ n < 2^k+1，那么ST表长度为k=floor(log2(n))。
ST查询：查询[L,R]区间的最值，区间长度k=floor(log2(R - L + 1))。查询以L为起点的长度2k，以R为终点的长度2^k，两个区间最值。
----------------------------------------Day4下午：排序进阶-----------------------------------------
一、分治（[NOIP2011 普及组] 瑞士轮）
对于一个规模为N的问题分解为M个规模较小的子问题。
该问题的规模缩小到一定的程度就可以容易的解决。
该问题可以分解为若干个规模较小的相同问题。
利用该问题分解出的子问题的解可以合并为总问题的解。
子问题的解相互独立，不会相同。
快速排序等使用了分治思想。
二、快速排序（T20472.【快速排序】升序）
利用分治思想，可以迅速将数列变得有序。
从序列中任选一个元素，设为x，x为基准值。（一般选择第一个元素）
调整位置，将x的左边全部小于x，x的右边全部大于x。
时间复杂度：最好情况O(nlogn)，最坏情况O(n)。（不具有稳定性）
三、归并排序（T20468.【归并排序】划分、T20467.【归并排序】合并…）
先划分，多次将一个数列分为两个部分。（根据中间值（(l+r)/2）分为两部分）
再合并，将划分后排序后的结果整合后输出。
时间复杂度：最好情况O(nlogn)，最坏情况O(n)。（不具有稳定性）
---------------------------------------Day5下午：特殊树与拓补排序----------------------------------------
一、完全二叉树（初赛知识）
若某二叉树深k层，除k层外其它层的结点总数达最大值，第k层结点数≤2^k-1并靠左侧连续，称为完全二叉树。
最后一层靠左侧连续，且其它层结点满，是完全二叉树；非最后一层结点总数未满，不是完全二叉树。
满二叉树是一类特殊的完全二叉树。
若完全二叉树结点总数为n，则：
n为奇数时，完全二叉树中没有度为1的结点，此时n=n0（叶子结点）+n2（有2个子节点的结点总数）；
n为偶数时，完全二叉树中一定只有一个度为1的结点，此时n=n0+n2+1。
n0=n2+1。
二、完全二叉树的性质及表示法（初赛知识）
具有n个结点的完全二叉树的深度为[log2(n)]（向下取整）+1。
若结点编号i=1，则结点i为根，无父节点；若i>1，则i的父节点编号为i/2。
针对编号为i的结点，其左孩子编号为2i（2i≤n）；其右孩子编号为2i+1（2i+1≤n）。
数组顺序存储法：当二叉树呈现完全二叉树性质时，以二叉树性质2为基础，可以用顺序数组来模拟二叉树。
即：tree[i]表示父节点，tree[2 * i]表示左孩子结点，tree[2 * i + 1]表示右孩子节点。
三、哈夫曼树（初赛知识）
在一棵树中，选择一个结点，它与根结点的通路称为路径。
路径中边的数目称为路径长度，若规定根结点的层数为1，则第L层结点到根节点的路径长度为L-1。
若将树中结点赋给一个有着某种意义的数值，则这个数值称为该结点的权。
该结点的路径长度与该结点权的乘积，为结点的带权路径长度。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL，哈夫曼树就是WPL值最小的树。
哈夫曼树通常以二叉树的形式出现，所以也称最优二叉树，是一类带权路径长度最小的树。
哈夫曼树使用了贪心策略。
对于给定有各自权值的n个结点，构造哈夫曼树的方法：
1.在n个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树的左右孩子；
2.删除使用过的两个权值，将新的权值加入到权值集合中；
3.重复第1和2步，直到无法再选出两个权值，这棵树就是哈夫曼树。
四、二叉搜索树（初赛知识）
二叉搜索树（BST）也称为二叉查找树、二分搜索树、有序二叉树或排序二叉树。
若它的左子树不为空，左子树上所有结点的值都小于它的根结点。
若它的右子树不为空，右子树上所有结点的值都大于它的根结点。
它的左、右子树也都是二叉搜索树。
对于给定有各自权值的n个结点，构造二叉搜索树的方法：
1.取出第一个结点作为根；
2.取出一个结点，与根比较，比根小的向左子树比较，比根大的向右子树比较；
3.到没有结点可以比较时，这个结点成为上次比较树结点的孩子；
4.重复第2和3步，直到结点都变成树结点，这棵树就是二叉搜索树。
五、拓扑排序（T20491.拓展二叉树）
拓扑排序要解决的问题是给一个有向无环图（DAG：边是有向的，没有形成闭环）的所有节点排序。
顶点表示活动，有向边表示活动之间的优先制约关系，(u,v)表示活动u必须先于活动v进行，称这种图有向图为AOV网。
顶点表示活动的网就是AOV网。
一个有向无环图的拓扑排序可能不唯一。
---------------------------------------Day6下午：动态规划----------------------------------------
一、动态规划的概念（初赛知识）
动态规划是一种表格处理法（记忆递归法），其分解的子问题重叠。
在对问题求解时，通过把原问题分解成相对简单的子问题的方式，求解复杂问题。
面对问题时选取多种策略中的最优解的行为即为“动态”；将原问题拆分成小问题的行为称为“规划”。
二、实现动态规划的过程（T20513.石子合并、T20512.打家劫舍…）
步骤：1.确定状态（读题）；2.划分阶段（规划）；3.确定状态转移方程（动态）。
三、区间动态规划（T20513.石子合并）
区间DP属于线性DP的一种，以区间长度作为DP的阶段，以区间的左右端点作为状态的维度。
一个状态通常由被它包含且比它更小的区间状态转移而来。
---------------------------------------Day7下午：背包问题----------------------------------------
本课是基于DP的一种数学算法，无固定格式和笔记。（真的不是我懒，而是老师没笔记！）
--------------------------------------Day8下午：综合动态规划----------------------------------------
一、序列DP（T20551.最长上升子序列、T20552.最大子段和、T20553.最长公共子序列…）
一般指将动态规划算法用于数组或者字符串上，进行相关具体问题的求解。
给定数组，求最长/最大的某种值；给定两个字符串，求最长/最大的某种值。
序列DP需要满足动态规划的三种重要条件。
对于数组相关的问题，其状态通常是一维的，类似地，我们也可以定义状态dp[i]记录数组的前i个数的最优值。
对于字符串相关的问题，通常我们需要定义一个二维状态dp[i][j]，记录两个字符串s1的第i个字符和s2的前j个字符之间的最优值。
子序列指的是数列中不一定连续但先后顺序一致的n个数字，即可去掉数列中的部分数字，但不可改变其前后顺序。
--------------------------------------Day9下午：树与表达式树----------------------------------------
一、树的存储(T20564.树的深度）
双亲表示法：利用树中除根结点外，每个结点都有唯一的父节点的性质。
其中，tree[i].parent表示编号为i的树结点的父亲。
孩子表示法：每个结点存储自己孩子的位置信息。（可选择vector存储）
其中，tree[i].child存储着结点i的孩子的位置信息。
邻接表表示法：邻接表主要是记录一个顶点的邻接点和邻接边信息的结构。
构造一个长度为顶点个数的vector数组G[]，对于G[i]存储顶点i的所有邻居。
二、算术表达式（初赛知识、T20570.表达式树求值）
分为前缀表达式（波兰式）、中缀表达式、后缀表达式（逆波兰式）。
前缀表达式的运算符放在操作符前面；中缀表达式的运算符放在操作符中间；后缀表达式的运算符放在操作符后面。
计算方法：使用栈（遇到操作数直接加入表达式、遇到界限符“(”入栈、遇到界限符“)”出栈、遇到运算符弹栈计算）、表达式树。
中缀->后缀：
1.根据运算符的优先级对中缀表达式加括号；
2.将运算符移到对应的括号后面；
3.去掉所有括号。
中缀->前缀：
1.根据运算符的优先级对中缀表达式加括号；
2.将运算符移到对应的括号前面；
3.去掉所有括号。
三、表达式树（初赛知识）
表达式树是一种特殊的树，它的非叶结点是操作符，叶结点是操作数。
因为操作符的操作数一般为两个，所以表达式树通常为二叉树。
可以使用栈的方法构建一棵后缀表达式树或前缀表达式树。
